from typing import List


class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        nums.sort()
        nums.reverse()
        # print(nums)
        sum_num = sum(nums)
        avg_num = sum_num // k
        if sum_num % k != 0:
            return False
        # print("avg: ", avg_num)
        now_all_result = []
        n = nums.pop(0)

        if n <= avg_num:
            now = [avg_num] * k
            now[0] = now[0] - n
            now_all_result.append(now)
        else:
            return False

        for num in nums:
            next_result = []
            # print("num:", num)
            # print(now_all_result)
            for last_result in now_all_result:
                hadDone = {}
                for i in range(k):
                    if last_result[i] - num >= 0 and hadDone.get(last_result[i]) is None:
                        hadDone[last_result[i]] = True
                        now = last_result.copy()
                        now[i] = now[i] - num
                        now.sort()
                        # print("now: ", now)
                        next_result.append(now)
            now_all_result = next_result

        return len(now_all_result) != 0


if __name__ == '__main__':
    # nums = [4, 5, 9, 3, 10, 2, 10, 7, 10, 8, 5, 9, 4, 6, 4, 9]
    # k = 5
    nums = [10, 1, 10, 9, 6, 1, 9, 5, 9, 10, 7, 8, 5, 2, 10, 8]
    k = 11
    s = Solution()

    print(s.canPartitionKSubsets(nums, k))

    # [2, 3, 4, 4, 4, 5, 5, 6, 7, 8, 9, 9, 9, 10, 10, 10]
    #
    # 10, 9, 2
    # 10, 8, 3
    # 10, 6, 5
    # [ 4, 4, 4, 5, 7, 9, 9]
    # 9, 7,5
    # 9 4 4 4
